每日算法 Day14

2023-04-29 01:42| 来源: 网络整理| 查看: 265

Leetcode 144.二叉树的前序遍历

题目链接：144.二叉树的前序遍历

1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 /** 递归法 17 class Solution { 18 public List preorderTraversal(TreeNode root) { 19 List result = new ArrayList(); 20 preorder(root, result); 21 return result; 22 } 23 24 public void preorder(TreeNode node, List result){ 25 if(node == null) return; 26 result.add(node.val); 27 preorder(node.left, result); 28 preorder(node.right, result); 29 } 30 } 31 */ 32 33 /** 迭代法非统一 34 class Solution{ 35 public List preorderTraversal(TreeNode root){ 36 List result = new ArrayList(); 37 if(root == null) return result; 38 39 Stack stack = new Stack(); 40 stack.push(root); 41 42 while(!stack.isEmpty()){ 43 TreeNode node = stack.pop(); // 中 44 result.add(node.val); 45 46 if(node.right != null) stack.push(node.right); // 右 47 if(node.left != null) stack.push(node.left); // 左 48 } 49 50 return result; 51 } 52 } 53 */ 54 55 // 迭代法统一 56 class Solution{ 57 public List preorderTraversal(TreeNode root){ 58 List result = new ArrayList(); 59 Stack stack = new Stack(); 60 if(root != null) stack.push(root); 61 62 while(!stack.isEmpty()){ 63 TreeNode node = stack.peek(); 64 if(node != null){ 65 stack.pop(); // 将节点弹出，避免重复操作；下面再按照右左中添加到栈中 66 if(node.right != null) stack.push(node.right); 67 if(node.left != null) stack.push(node.left); 68 69 stack.push(node); 70 stack.push(null); // 中节点访问过，但还没有处理，加入空节点作为标记 71 }else{ 72 stack.pop(); // 将空节点弹出 73 node = stack.peek(); // 重新取出栈中元素 74 stack.pop(); 75 result.add(node.val); 76 } 77 } 78 79 return result; 80 } 81 }

小结：（1）这里写了递归法、迭代法非统一、迭代法统一三种方法。（2）递归法：中左右；迭代法非统一：入栈顺序为中右左；迭代法统一：入栈顺序为右左中，且每次访问中节点后需要再加入一个空节点作为标记。

Leetcode 94.二叉树的中序遍历

题目链接：94.二叉树的中序遍历

1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 17 /** 递归法 18 class Solution { 19 public List inorderTraversal(TreeNode root) { 20 List result = new ArrayList(); 21 inorder(root, result); 22 return result; 23 } 24 25 public void inorder(TreeNode node, List result){ 26 if(node == null) return; 27 inorder(node.left, result); 28 result.add(node.val); 29 inorder(node.right, result); 30 } 31 } 32 */ 33 34 /** 迭代法非统一 35 class Solution{ 36 public List inorderTraversal(TreeNode root){ 37 List result = new ArrayList(); 38 if(root == null) return result; 39 40 Stack stack = new Stack(); 41 TreeNode cur = root; 42 while(cur != null || !stack.isEmpty()){ 43 if(cur != null){ 44 stack.push(cur); 45 cur = cur.left; 46 }else{ 47 cur = stack.pop(); 48 result.add(cur.val); 49 cur = cur.right; 50 } 51 } 52 53 return result; 54 } 55 } 56 */ 57 58 // 迭代法统一 59 class Solution{ 60 public List inorderTraversal(TreeNode root){ 61 List result = new ArrayList(); 62 Stack stack = new Stack(); 63 if(root != null) stack.push(root); 64 65 while(!stack.isEmpty()){ 66 TreeNode node = stack.peek(); 67 if(node != null){ 68 stack.pop(); // 下面按照右中左添加到栈中 69 70 if(node.right != null) stack.push(node.right); 71 72 stack.push(node); 73 stack.push(null); 74 75 if(node.left != null) stack.push(node.left); 76 }else{ 77 stack.pop(); 78 node = stack.peek(); 79 stack.pop(); 80 result.add(node.val); 81 } 82 } 83 84 return result; 85 } 86 }

小结：（1）递归法：左中右；迭代法非统一：需要先遍历到左叶子节点—左，弹出当前节点保存结果—中，遍历当前节点的右子节点—右；迭代法统一：入栈顺序为右中左，且每次访问中节点后需要再加入一个空节点作为标记。

Leetcode 145.二叉树的后序遍历

题目链接：145.二叉树的后序遍历

1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 /** 递归法 17 class Solution { 18 public List postorderTraversal(TreeNode root) { 19 List result = new ArrayList(); 20 postorder(root, result); 21 return result; 22 } 23 24 public void postorder(TreeNode node, List result){ 25 if(node == null) return; 26 postorder(node.left, result); 27 postorder(node.right, result); 28 result.add(node.val); 29 } 30 } 31 */ 32 33 /** 迭代法非统一 34 class Solution{ 35 public List postorderTraversal(TreeNode root){ 36 List result = new ArrayList(); 37 if(root == null) return result; 38 39 Stack stack = new Stack(); 40 stack.push(root); 41 42 while(!stack.isEmpty()){ 43 TreeNode node = stack.pop(); // 中 44 result.add(node.val); 45 46 if(node.left != null) stack.push(node.left); // 左 47 if(node.right != null) stack.push(node.right); // 右 48 } 49 50 Collections.reverse(result); 51 return result; 52 } 53 } 54 */ 55 56 // 迭代法非统一 57 class Solution{ 58 public List postorderTraversal(TreeNode root){ 59 List result = new ArrayList(); 60 Stack stack = new Stack(); 61 if(root != null) stack.push(root); 62 63 while(!stack.isEmpty()){ 64 TreeNode node = stack.peek(); 65 if(node != null){ 66 stack.pop(); // 下面按照中右左添加到栈中 67 68 stack.push(node); 69 stack.push(null); 70 71 if(node.right != null) stack.push(node.right); 72 if(node.left != null) stack.push(node.left); 73 }else{ 74 stack.pop(); 75 node = stack.peek(); 76 stack.pop(); 77 result.add(node.val); 78 } 79 } 80 81 return result; 82 } 83 }

小结：（1）递归法：左右中；迭代法非统一：入栈顺序为中左右，保存的结果顺序为中右左，最后将结果反转，即左右中；迭代法统一：入栈顺序为中右左，且每次访问中节点后需要再加入一个空节点作为标记。

【本文地址】

公司简介

联系我们